/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
    public:
    /**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        string s, t;
        while(head1)
        {
            s += head1->val + '0';
            head1 = head1->next;
        }
        while(head2)
        {
            t += head2->val + '0';
            head2 = head2->next;
        }
        string res = solve(s, t);
        // cout << res;
        if(res.size() == 0)
        {
             return nullptr;
        }
        ListNode* cur;
        cur = new ListNode(res[0] - '0');
        ListNode* ret = cur;
        for(int i = 1; i < res.size(); ++i)
        {
            ListNode* tmp = new ListNode(res[i] - '0');
            cur->next = tmp;
            cur = cur->next;
        }
        cur->next = nullptr;
        return ret;
    }
    string solve(string s, string t) {
        int end1 = s.size() - 1, end2 = t.size() - 1;
        string ret;
        int carry = 0;
        while(end1 >= 0 || end2 >= 0)
        {
            int val1 = end1 >= 0 ? s[end1] - '0' : 0;
            int val2 = end2 >= 0 ? t[end2] - '0' : 0;
            ret += (val1 + val2 + carry) % 10 + '0';
            if(val1 + val2 + carry > 9)
            {
                carry = 1;
            }
            else
            {
                carry = 0;
            }
            --end1;
            --end2;
        }
        if(carry)
        {
            ret += '1';
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};